lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Merge sort.md (328B)

      1 +++
      2 title = 'Merge sort'
      3 +++
      4 # Merge sort
      5 belongs to “divide and conquer”
      6 
      7 1. if only one element remaining in list, it is sorted — return
      8 2. divide list recursively into two halves until no longer divided
      9 3. merge smaller list into new list in sorted order
     10 
     11 Time complexity:
     12 
     13 - Best case: O(nlogn)
     14 - Worst case: O(nlogn)